package pen_exam.smallblackbox_2024_03_15;


//给城市起别名，按顺序删除后保留三个字母，不能和其他城市冲突，返回是否能全部命名
//思路：求最长公共子序列，用长度-最长公共子序列长度，若>3即可
public class Class02_CityName {
    public static boolean cityName(String[] cityName){
        int N = cityName.length;
        int[] length = new int[N];
        for (int i = 0;i < N;i++) length[i] =  cityName[i].length();
        for(int i = 0;i < N;i++){
            String s1 = cityName[i];
            for(int j = i + 1;j < N;j++){
                String s2 = cityName[j];
                int len = longestCommonSubsequence(s1,s2);
                length[i] = Math.min(length[i],s1.length() - len);
                length[j] = Math.min(length[j],s2.length() - len);
            }
        }
        for (int i = 0; i < N; i++) {
            if(length[i] < 3) return false;
        }
        return true;
    }
    public static int longestCommonSubsequence(String s1,String s2){
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        return process(str1,str2,0,0);
    }
    public static int process(char[] str1,char[] str2,int i,int j){
        if(i == str1.length || j == str2.length){
            return 0;
        }
        int p1 = 0;//匹配
        int p2 = 0;//不匹配
        if(str1[i] == str2[j]){
            p1 = 1 + process(str1,str2,i+1,j+1);
        }
        p2 = Math.max(process(str1,str2,i+1,j),process(str1,str2,i,j+1));
        return Math.max(p1,p2);
    }

    public static void main(String[] args) {
        String[] cityName = {"ABCD","DEG"};

        System.out.println(cityName(cityName));
    }
}
